require "trees/heap.rb"
require "utils/utils.rb"

# This class is waaaay cleaner than the f***in' Java counterpart.
# Really horrible counterpart.
class MergeSort
  def MergeSort.sort(source, division_factor)
    if source.size < division_factor
      source.sort
    else
      sub_arrays = split_array(source, division_factor)
      for i in (0...sub_arrays.size)
        sub_arrays[i] = sort(sub_arrays[i], division_factor)
      end
      
      iterative_sort(sub_arrays); # return
    end
  end
  
  def MergeSort.iterative_sort(arrays)
    sorted = []
    heap = Heap.new {|arr0, arr1| arr0.first < arr1.first }
    
    arrays.each {|array| heap.insert(array) }
    
    while heap.size > 0
      next_source = heap.extract_top
      sorted.push(next_source.delete_at(0))
      
      heap.insert(next_source) unless next_source.size == 0
    end
    
    sorted
  end
end